NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/1811

Internet Message Format | 1996-08-06 | 1.8 KB

Path: rap.SanDiegoCA.ATTGIS.COM!es013!jbc
From: [e-mail] (Jim Chapman)
Newsgroups: comp.lang.c++
Subject: Re: deque container - how to implement?
Date: 13 Jan 1996 01:26:42 GMT
Organization: AT&T Global Information Solutions
Distribution: world
Message-ID: <4d71oi$[e-mail]>
References: <4d4c73$[e-mail]>
Reply-To: [e-mail]
NNTP-Posting-Host: es013.elsegundoca.attgis.com

In article [e-mail], [e-mail]  ( Todd Knarr ) writes:
> In <4d1of1$[e-mail]>, [e-mail] (Jim Chapman) writes:
> >In STL, deque<T> is supposed to support random access in constant time, so
> >a linked list implemention wouldn't do.  The first poster was closer to
> >the mark.
>
> If you want constant-time access, an array is the only way to implement
> it. Unfortunately then your insert time can skyrocket unexpectedly when
> you have to copy the entire pointer array to a bigger array. It can also
> fail completely if you can't allocate the bigger array ( the non-intrusive
> linked-list form can also fail like that, it's just less likely because of
> the smaller blocks of memory involved ). It's a trade-off between the
> operations needed, memory space used, access time and insert time.
>
The implementation of a deque uses arrays to provide constant-time
access, but adds one level of indirection to gain the storage flexibility
that allows inserts at either end (but not in the middle) to execute
in constant time.

 ---
 ====  AT&T        | Jim Chapman             |
=--=== Global      | Multimedia Projects     | [e-mail]
=--=== Information | 100 N. Sepulveda Blvd.  |   Voice: [phone]
 ====  Solutions   | El Segundo, CA 90245    |   FAX:   [phone]